package types;

import java.util.ArrayList;
import java.util.Hashtable;
import java.util.Random;

public class Algorithms extends Parser {

	static Solution solution;
	static short location;
	static ArrayList <Short> location_tracker;

	/* 
	 * start with first edge that was in input file
	 * see how many edges it has that can travel to available vertices
	 * 		recurse based on the number of available
	 *  */


	public static Solution branched_greedy ()
	{	
		solution = new Solution();
		solution.edges.ensureCapacity(Main.vertex_list.size()-1);
		ArrayList<Solution> solutions = new ArrayList <Solution> ();
		location_tracker = new ArrayList <Short> ();
		location_tracker.ensureCapacity(Main.vertex_list.size()-1);
		Solution temp = new Solution();

		location = 1;
		location_tracker.add(location);
		updateValidsTraversal(Algorithms.location);

		for (short a = 0; a < 2; a++){
			recurse(a);
			for (short b = 0; b < 2; b++){
				recurse(b);
				for (short c = 0; c < 2; c++){
					recurse(c);
					for (short d = 0; d < 2; d++){	
						recurse(d);
						for (short e = 0; e < 2; e++){	
							recurse(e);
							for (short f = 0; f < 2; f++){	
								recurse(f);
								for (short g = 0; g < 2; g++){
									recurse(g);
									for (short h = 0; h < 2; h++){
										recurse(h);
										for (short i = 0; i < 2; i++){
											recurse(i);
											for (short j = 0; j < 2; j++){
												recurse(j);
												for (short counter = (short) ((Main.vertex_list.size() - Main.branching ) - 2); counter > 0; counter--)
												{
													recurse((short) 0);
												}

												temp = new Solution(new ArrayList <Edge> (solution.edges), sol_dist(solution, 0));

												solutions.add(temp);
												temp = return_min(solutions);
												solutions.clear();
												solutions.add(temp);


												//print_edges(Main.vertex_list);

												location_tracker = new ArrayList <Short> (location_tracker.subList(0,Main.branching));
												solution = new Solution (new ArrayList <Edge> (solution.edges.subList(0, Main.branching)), 0);
												resetValids();

												solution.edges.remove(solution.edges.size()-1);
												//location_tracker.remove(location_tracker.size()-1);
												location = location_tracker.get(location_tracker.size()-1);

											}
											removeAndUpdate();
										}
										removeAndUpdate();
									}
									removeAndUpdate();
								}
								removeAndUpdate();
							}
							removeAndUpdate();
						}
						removeAndUpdate();
					}
					removeAndUpdate();
				}
				removeAndUpdate();
			}
			removeAndUpdate();
		}

		if(solutions.get(0) == null) {System.out.println("solution couldn't be found");}

		return (solutions.get(0));
	}

	// performs 2 opt switches for every edge of weight greater than weight variable
	// doesnt replace with optimal, just replaces after first found improvement
	// doesn't go back to the start of the list, keeps going to end
	// have some sort of counter and return when a full loop has passed and no modifications made, increment when a modification made
	public static void two_opt (int weight)
	{

		int next = 1;			// points to the location of the next edge in the solution

		Edge A_B = null;		// edge we don't like
		Edge C_D = null;		// edge reachable from a destination vertex (A, V) or (B, V)

		Edge A_C = null;
		Edge B_D = null;

		Hashtable <Integer, Short[]> possible_switches = new Hashtable <Integer, Short[]> ();
		Hashtable <Integer, Edge[] > edge_keeper = new Hashtable <Integer, Edge[]> ();

		int replacement_weight;
		long goal; 				// total weight we want to beat

		/* (-> = edge, we have A -> B and C -> D and seeing C -> A or D -> B 
		is possible and takes less weight, if yes, switch) */
		short A, B, C, D;		

		boolean run = true;		// keep running if a modification has been made
		boolean breakout = false;  // have we found our edge replacements?

		while(run){
			run = false;
			// search for edge with weight greater than parameter
			for(int i = 1; i < solution.edges.size()-1; i++)
			{
				breakout = false;
				// if A -> B is bad
				//System.out.println("edge: " + solution.edges.get(next).toString());

				A_B = solution.edges.get(next);
				next = solution.edges.get(next).getDestination();
				if (next == 1) {break;}
				if (A_B.weight > weight)
				{
					A = A_B.getSource();
					B = A_B.getDestination();


					//System.out.println("A -> B: " + A_B.toString());

					// finding A -> C
					for (int j = 1; j < Main.vertex_list.get(A).edges.size() && !breakout; j++)
					{
						A_C = Main.vertex_list.get(A).edges.get(j);
						C = A_C.getDestination();
						//System.out.println("A -> C: " + A_C.toString());
						// find C -> D
						C_D = Main.solution.edges.get(C);
						D = C_D.getDestination();		
						// does B -> D exist? obviously A -> C exists
						for(int m = 0; m < Main.vertex_list.get(D).edges.size() /*&& !breakout*/; m++)
						{
							//if (possible_switches.size() == 3) { break; }


							if (Main.vertex_list.get(D).edges.get(m).getDestination() == B)
							{
								B_D = Main.vertex_list.get(D).edges.get(m);
								//System.out.println("B -> D: " + B_D.toString());
								replacement_weight = (A_C.weight + B_D.weight);
								goal = (long) (A_B.weight + C_D.weight);

								//String swap_move = A+B + ", " + C+D + " vs " + A+C + ", " + B + D; 

								if (goal > replacement_weight && !possible_switches.contains(replacement_weight))
								{
									Short[] vertex = {A,B,C,D} ;
									Edge[] temp_edge = { A_C, B_D };
									edge_keeper.put(replacement_weight, temp_edge); 
									possible_switches.put(replacement_weight, vertex);

								}


							}
						}
						// end of finding possible edges

						if(!possible_switches.isEmpty())
						{
							Object[] keys = possible_switches.keySet().toArray();
							int key = (Integer) keys[0];
							for(int y = 1; y < keys.length; y++)
							{
								int key_temp = (Integer) keys[y];
								if (key < key_temp) { key = key_temp; }
							}
							Short[] vertex = possible_switches.get(key) ;
							Edge[] temp_edge = edge_keeper.get(key);
							updateSolution(vertex[0], vertex[1], vertex[2], vertex[3], temp_edge[0], temp_edge[1]);

							edge_keeper.clear();
							possible_switches.clear();

							run = true;
							breakout = true;
							next = 1;

						}

					}

				}									
			}
		}
	}

	public static void remove (ArrayList <Edge> mutation_set)
	{
		Edge A_B = null;		// edge we don't like
		Edge C_D = null;		// edge reachable from a destination vertex (A, V) or (B, V)

		Edge A_C = null;
		Edge B_D = null;

		int replacement_weight;
		long goal; 				// total weight we want to beat
		boolean removed;

		/* (-> = edge, we have A -> B and C -> D and seeing C -> A or D -> B 
		is possible and takes less weight, if yes, switch) */
		short A, B, C, D;		

		for(int i = 0; i < mutation_set.size(); i++)
		{	
			removed = false;
			A_B = mutation_set.get(i);
			A = A_B.getSource();
			B = A_B.getDestination();
			// A -> C
			for(int j = 0; j < Main.vertex_list.get(A).edges.size()-1 ; j++)
			{
				A_C = Main.vertex_list.get(A).edges.get(j);
				C = A_C.getDestination();
				// find C -> D
				C_D = Main.solution.edges.get(C);
				D = C_D.getDestination();
				// does B -> D exist? obviously A -> C exists
				for(int m = 0; m < Main.vertex_list.get(D).edges.size(); m++)
				{
					if (Main.vertex_list.get(D).edges.get(m).getDestination() == B)
					{
						B_D = Main.vertex_list.get(D).edges.get(m);
						replacement_weight = (A_C.weight + B_D.weight);
						goal = (long) (A_B.weight + C_D.weight);
						if (goal > replacement_weight)
						{
							System.err.println("yay, updating a city");
							updateSolution(A,B,C,D,A_C,B_D);
							removed = true;
							break;
						}
					}
				}
				if (removed) { break; }
			}
			if (!removed)
			{
				if(A_B.getWeight() != Main.max_weight) { return; }
				System.err.println("darn, mutating a city");
				mutate(A_B);
			}
		}
		mutation_set.clear();
	}

	public static void mutate (Edge e)
	{
		Edge A_B = null;		// edge we don't like
		Edge A_C = null;
		Edge C_D = null;		// edge reachable from a destination vertex (A, V) or (B, V)
		Edge B_D = null;
		
		short A, B, C, D;
		
		A = e.getSource();
		B = e.getDestination();
		
		Random random = new Random();
		int rand = 0;
		while(rand < 2) { rand = random.nextInt(Main.vertex_list.size()-1); }
		
		if (Main.vertex_list.get(A).edges.get(0).getSource() != 1)
		{
			A_C = Main.vertex_list.get(A).edges.get(0);
		}
		else 
		{
			if(Main.vertex_list.get(A).edges.size() < 1 ) { return; }
			A_C = Main.vertex_list.get(A).edges.get(1);
		}
		
		while(rand < 2) { rand = random.nextInt(Main.vertex_list.size()-1); }
		
		C = A_C.getDestination();
		// find C -> D
		C_D = Main.solution.edges.get(C);
		D = C_D.getDestination();
		if (D == 1) { return; }
		
		// create B_D
		B_D = new Edge (B, (short) rand, Main.max_weight);
		
		System.err.println("updating from mutate");
		updateSolution(A,B,C,D,A_C,B_D);

	}

}